#! /usr/bin/env python
# -*- coding: utf-8 -*-



# =================== function  =====================
def kmp_match(src, target):
    if src is None or target is None:
        return -1

    if target == '':
        return 0

    if src == '':
        return -1

    match_move_len = kmp_compile_target(target)
    return match_compilted_target(src, target, match_move_len)

def match_compilted_target(src, target, match_move_len):
    src_len = len(src)
    target_len = len(target)
    src_from = 0

    while src_len - src_from >= target_len:
        same_len = same_pre_len(src, src_from, target)
        if same_len == target_len:
            return src_from
        else:
            src_from += match_move_len[same_len]

    return -1

def same_pre_len(src, src_idx_from, target):
    assert len(target) <= len(src) - src_idx_from

    same_len = 0
    for i in range(len(target)):
        if src[src_idx_from + i] == target[i]:
            same_len += 1
        else:
            break

    return same_len

def kmp_compile_target(target):
    # 计算长度为1 到长度为len(target)-1的子串的max_same_pre
    tar_len = len(target)
    assert tar_len >= 1

    result = {}          # (sub_match_len, move_len)
    result[0] = 1        # 如果没有匹配字符, 必须移动到下一位
    result[1] = 1        # 如果只匹配到1位字符, 必须移动到下一位

    '''
        target = 'abcabc__', 匹配到'abcabc', 下次移动3位即可
    '''
    # 2 --> tar_len-1 (NOTE: tar_len无意义, 因为表示全匹配)
    for sub_match_len in range(2, tar_len):
        max_same_pre_len = calc_max_pre_len(target[:sub_match_len])
        move_len = sub_match_len - max_same_pre_len
        # ele = (sub_match_len, move_len)
        result[sub_match_len] = move_len

    return result

'''
'aa' ------> 1
'ab' ------> 0
'aba' ------> 1
'abcdefg_abc' ------> 3
'''
def calc_max_pre_len(s):
    src_len = len(s)
    assert src_len >= 2      # 1 无意义

    # src_len -1 ------> 1
    for sub_len in range(src_len-1, 0, -1):
        # 从最长开始匹配
        if s[:sub_len] == s[-sub_len:]:
            return sub_len

    return 0


# =================== solution  =====================
class Solution:
    def strStr(self, source, target):
        return kmp_match(source, target)


def main():
    print("start main")

    s = Solution()
    r = s.strStr('', '')
    # r = s.strStr('asdf', 'sd')
    # r = s.strStr('asdf', 'df')
    print(r)

if __name__ == "__main__":
    main()
